60E - Mushroom Gnomes - CodeForces Solution

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define no_answer {cout << "NO"; exit(0);}
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)

const long long mxn = 1e6 + 110;
const long long mnn = 1e3 + 2;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
const long long OO = 1e9;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

llong n, x, y, p, ini[mxn];
vector<llong> v(5, 0);

vector<vector<llong> > mul(vector<vector<llong> > a, vector<vector<llong> > b){
    vector<vector<llong> > ans(5, vector<llong> (5, 0));
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 5; k++){
                ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % p;
            }
        }
    }
    return ans;
}

vector<vector<llong> > sym(){
    vector<vector<llong> > lol(5, vector<llong> (5, 0));
    for(int i = 0; i < 5; i++) lol[i][i] = 1;
    return lol;
}

vector<vector <llong > > binpow(vector<vector<llong> > a, llong k){
    if(k == 0){
        return sym();
    }else if(k % 2 == 1){
        return mul(binpow(a, k - 1), a);
    }else{
        vector<vector<llong> > x = binpow(a, k / 2);
        return mul(x, x);
    }
}

vector<llong> going_to_havchik(vector<llong> v, llong k){
    vector<vector<llong> > mat(5, vector<llong> (5, 0));
    mat[0][0] = 1;
    mat[1][0] = mat[1][4] = -1;
    mat[1][1] = 3;
    mat[2][3] = mat[3][2] = mat[3][3] = 1;
    mat[4][4] = 1;
    mat = binpow(mat, k);
    vector<llong> nw(5, 0);
    for(int i = 0; i < 5; i++){
        for(int k = 0; k < 5; k++){
            nw[i] = (nw[i] + mat[i][k] * v[k]) % p;
            nw[i] = (nw[i] + p) % p;
        }
    }
    return nw;
}

int main(){
    ios;
    cin >> n >> x >> y >> p;
    for(int i = 1; i <= n; i++){
        cin >> ini[i];
        ini[i] %= p;
        v[1] = (v[1] + ini[i]) % p;
    }
    if(n == 1){
        cout << ini[1];
        return 0;
    }
    v[0] = ini[1], v[4] = ini[n];
    v[2] = ini[n - 1];
    v[3] = ini[n];
    
    v = going_to_havchik(v, x);
    v[4] = v[3];
    v = going_to_havchik(v, y);
    
    cout << v[1] ;
}